package com.feiyue.learning.graph;

import java.util.Scanner;

/**
 * 割点：在无向连通图中，删除某个顶点导致图不在连通则称这个点为割点（下图, 3就是割点）
 *
 *  1---2
 *   - -
 *    3
 *   - -
 *  4---5
 * @author  feiyue
 * @date  2020/4/6
 */
public class CutPoint {

    // 定义数组存放割点
    static int[] flag = new int[6];

    // 访问时间戳
    static int index = 0;

    // 顶点数
    static int n = 5;

    // 边数
    static int m = 6;

    // 根结点编号
    static int root = 1;

    static int[][] edges = new int[7][7];

    // num[i] 记录访问顶点 i 的时间戳, 第一个顶点为 1
    static int[] num = new int[6];

    // low[i] 记录不经过父顶点能够访问到的最早时间戳
    static int[] low = new int[6];

    public static void main(String[] args) {

        // 图边初始化
        for (int i = 1; i <= m; i++) {
            Scanner sc = new Scanner(System.in);
            int start = sc.nextInt();
            int end = sc.nextInt();

            // start-->end 这条边是连通的
            edges[start][end] = 1;
            edges[end][start] = 1;
        }

        // 从 1 号顶点开始深度优先遍历
        dfs(1, root);

        System.out.println("割点如下：");
        for (int i : flag) {
            System.out.print(i + "");
        }
    }

    /*
     * 割点算法的核心
     *      cur: 当前顶点
     *      parent: 当前顶点的父顶点(深度遍历较当前顶点更早一次遍历的顶点)
     */
    private static void dfs(int cur, int father) {

        // 当前顶点的子结点数
        int child = 0;

        index++;

        num[cur] = index;
        low[cur] = index;

        for (int i = 1; i <= n; i++) {

            // i 顶点和 cur 相连
            if (edges[cur][i] == 1) {

                // i 的时间戳为 0, 表示未被访问
                if (num[i] == 0) {
                    child++;
                    dfs(i, cur);

                    // 更新当前顶点可以访问的最早顶点时间戳
                    low[cur] = min(low[cur], low[i]);

                    // 如果当前顶点不是根节点并且满足 low[i] >= num[cur], 则当前顶点是割点
                    if (cur != root && low[i] >= num[cur]) {
                        flag[cur] = 1;
                    }

                    // 如果当前顶点是根节点, 且含有两个子结点, 则是割点
                    if (cur == root && child == 2) {
                        flag[cur] = 1;
                    }
                } else if (i != father) {
                    // 该节点曾经被访问过, 并且这个结点不是当前顶点的父顶点, 则需要更新 cur 可访问的最早顶点时间戳
                    low[cur] = min(low[cur], num[i]);
                }
            }
        }
    }

    private static int min(int a, int b) {
        return a > b ? b : a;
    }
}
